package com.jxb.four;

import com.jxb.tree.TreeNode;

/**
 * 二叉树中的最大路径和
 * 输入：root = [-10,9,20,null,null,15,7]
 * 输出：42
 *
 *
 */
public class BTMaximumPathSum_124 {

    int maxValue = Integer.MIN_VALUE;

    public int maxPathSum(TreeNode root) {
        maxPathDown(root);
        return maxValue;
    }

    private int maxPathDown(TreeNode node) {
        if (node == null) {
            return 0;
        }
        //递归遍历左子树
        int left = Math.max(0,maxPathDown(node.left));
        //递归遍历右子树
        int right = Math.max(0,maxPathDown(node.right));

        //获取最大值
        maxValue = Math.max(maxValue,left+right+node.val);
        //返回以当前节点为根的树的节点值之和
        return Math.max(left,right) + node.val;
    }

}
